\relax 
\citation{url:facebook}
\citation{bailly-bechet:finding}
\citation{kang:pegasus}
\citation{malewicz:pregel}
\citation{chan:cgmlib}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}large-scale graph mining}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}graph partitioning}{\thepage }}
\citation{kl:partition}
\citation{barnard:mrsb}
\citation{karypis:multi1}
\citation{url:streaming}
\citation{kl:partition}
\citation{1585498}
\citation{barnard:mrsb}
\citation{tech:sparspak}
\citation{Gary:amp}
\citation{karypis:multi1}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.3} overview of our approach}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.4} contributions}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {2}Related work}{\thepage }}
\citation{sui:parallel}
\citation{w.hagen:new}
\citation{wagner:mincut}
\citation{gn:community}
\citation{kl:partition}
\citation{barnard:mrsb}
\citation{Raghavan2007Near}
\@writefile{toc}{\contentsline {section}{\numberline {3}Preliminaries}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Graph notation}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Graph partitioning}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {4}Multi-level stepwise partitioning algorithm}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Overview of the Multilevel Paradigm}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Weighted label propagation}{\thepage }}
\citation{dean:mapreduce:}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces A partition example on synthetic graph.}}{\thepage }}
\newlabel{fig:partition example}{{1}{\thepage }}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Weighted label propagation on MapReduce.}}{\thepage }}
\newlabel{fig:wlp}{{2}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Implementation on MapReduce}{\thepage }}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Construct the upper level graph.}}{\thepage }}
\newlabel{fig:upper}{{3}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.4}Stepwise minimizing RatioCut Algorithm}{\thepage }}
\newlabel{pro:mono}{{1}{\thepage }}
\citation{Berkeley:spark}
\citation{barabasi:emergence}
\citation{small-world-watts-strogatz}
\citation{Holme2002}
\citation{url:networkx}
\citation{url:snap}
\citation{url:gpa}
\citation{Hendrickson_Leland_1994}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Greedy Algorithm for minimizing $PRC$.}}{\thepage }}
\newlabel{algo:greedy}{{1}{\thepage }}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Stepwise partitioning Algorithm.}}{\thepage }}
\newlabel{algo:par}{{2}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {5}Experimental evaluation}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Hardware Description}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Dataset Description}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}Experimental Results}{\thepage }}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.3.1}Performance of partitioning algorithm}{\thepage }}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Networks Basic Structural Properties.}}{\thepage }}
\newlabel{table:dataset}{{1}{\thepage }}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.3.2}Scalability of partitioning algorithm}{\thepage }}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces The fraction of edges cut of the different partition algorithm.}}{\thepage }}
\newlabel{fig:per}{{4}{\thepage }}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces The fraction of edges cut of 10 Watts-Strogatz graphs using different algorithms.}}{\thepage }}
\newlabel{fig:datasize}{{5}{\thepage }}
\citation{Berkeley:spark}
\citation{malewicz:pregel}
\citation{yucheng:graphlab}
\citation{malewicz:pregel}
\bibstyle{abbrv}
\bibdata{partition}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces The fraction of edges cut of the Watts-Strogatz graph with different partition number.}}{\thepage }}
\newlabel{fig:parNum}{{6}{\thepage }}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Runtime of 10 Watts-Strogatz graphs with 32 reducers. }}{\thepage }}
\newlabel{fig:runtime}{{7}{\thepage }}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.3.3}Results on a real system}{\thepage }}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Runtime of algorithm with different reducer number.}}{\thepage }}
\newlabel{fig:reducerNum}{{8}{\thepage }}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces The averaged runtime of a PageRank iteration with different partitioning approach.}}{\thepage }}
\newlabel{table:par}{{2}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {6}Conclusions}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {7}Acknowledgments}{\thepage }}
\bibcite{bailly-bechet:finding}{1}
\bibcite{barabasi:emergence}{2}
\bibcite{barnard:mrsb}{3}
\bibcite{tech:sparspak}{4}
\bibcite{chan:cgmlib}{5}
\bibcite{wagner:mincut}{6}
\bibcite{dean:mapreduce:}{7}
\bibcite{url:facebook}{8}
\bibcite{1585498}{9}
\bibcite{gn:community}{10}
\bibcite{w.hagen:new}{11}
\bibcite{Hendrickson_Leland_1994}{12}
\bibcite{Holme2002}{13}
\bibcite{kang:pegasus}{14}
\bibcite{karypis:multi1}{15}
\bibcite{kl:partition}{16}
\bibcite{url:snap}{17}
\bibcite{yucheng:graphlab}{18}
\bibcite{malewicz:pregel}{19}
\bibcite{Gary:amp}{20}
\bibcite{Raghavan2007Near}{21}
\bibcite{url:networkx}{22}
\bibcite{url:streaming}{23}
\bibcite{sui:parallel}{24}
\bibcite{url:gpa}{25}
\bibcite{small-world-watts-strogatz}{26}
\bibcite{Berkeley:spark}{27}
\@writefile{toc}{\contentsline {section}{\numberline {8}References}{\thepage }}
